from math import *
import matplotlib.pyplot as plt
import numpy


def dist_for_float(p1, p2):
    dist = 0.0
    elem_type = type(p1)
    # print(elem_type)
    if elem_type == numpy.float64 or elem_type == int:
        dist = float(abs(p1 - p2))
    else:
        sumval = 0.0
        for i in range(len(p1)):
            sumval += pow(p1[i] - p2[i], 2)
        dist = pow(sumval, 0.5)
    return dist


def display(s1, s2):
    val, path = DTW(s1, s2)

    w = len(s1)
    h = len(s2)

    mat = [[1] * w for i in range(h)]
    for node in path:
        [x, y] = node
        mat[x][y] = 0

    mat = numpy.array(mat)

    plt.subplot(2, 2, 2)
    c = plt.pcolor(mat, edgecolors='k', linewidths=4)
    plt.title('Dynamic Time Warping (%f)' % val)

    plt.subplot(2, 2, 1)
    plt.plot(s2, range(len(s2)), 'g')

    plt.subplot(2, 2, 4)
    plt.plot(range(len(s1)), s1, 'r')

    plt.show()



def DTW(s1,s2):

    w = len(s1)
    h = len(s2)

    mat = [([0 for j in range(w)]) for i in range(h)]

    for x in range(w):
        for y in range(h):
            dist = dist_for_float(s1[x], s2[y])
            mat[y][x] = dist
    # print(mat)

    dis = [([mat[0][0] for j in range(w)]) for i in range(h)] #累加距离矩阵

    for x in range(1, w):
        dis[0][x] = mat[0][x] + dis[0][x-1]

    for y in range(1, h):
        dis[y][0] = mat[y][0] + dis[y-1][0]

    for j in range(1,h):
        for i in range(1,w):
            dis[j][i] = mat[j][i] + min(dis[j][i-1],dis[j-1][i],dis[j-1][i-1])

    path = []
    path.append([h-1,w-1])

    for i in range(w+h):
        temp = min(dis[path[i][0] - 1][path[i][1]], dis[path[i][0]][path[i][1] - 1],dis[path[i][0] - 1][path[i][1] - 1])
        # print(temp)
        if path[i][0]==0 and path[i][1]==0:
            break
        if temp==dis[path[i][0]-1][path[i][1]-1]:
            path.append([path[i][0]-1,path[i][1]-1])
        elif temp==dis[path[i][0]-1][path[i][1]]:
            path.append([path[i][0]-1,path[i][1]])
        elif temp==dis[path[i][0]][path[i][1]-1]:
            path.append([path[i][0],path[i][1]-1])

    # print(path)

    return dis[h-1][w-1],path
    # return dis[h-1][w-1]


# s1 = [1, 2, 3, 4, 5, 5, 5, 4]
# s2 = [3, 4, 5, 5, 5, 4]
# # s2 = [1, 2, 3, 4, 5, 5]
# s2 = [2, 3, 4, 5, 5, 5]

# s2 = [8,9,1]
# s1 = [2,5,4,6]

# display(s1, s2)
# print(DTW(s1,s2))
